import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @program: LeetCode
 * @description: LeetCode : 剑指 Offer II 061. 和最小的 k 个数对
 * @author: WXY
 * @create: 2023-01-06 09:38
 * @Version 1.0
 **/
public class offer_twenty3_kSmallestPairs {
    public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> list = new ArrayList<>();
        PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return (o1[1] + o1[0]) - (o2[0] + o2[1]);
            }
        });
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                heap.offer(new int[]{nums1[i], nums2[j]});
            }
        }
        k = Math.min(k, heap.size());
        for (int i = 0; i < k; i++) {
            ArrayList<Integer> curList = new ArrayList<>();
            int[] poll = heap.poll();
            curList.add(poll[0]);
            curList.add(poll[1]);
            list.add(curList);

        }
        return list;
    }

}
